package 题目集.动态规划.背包问题;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.BitSet;

/**
 * https://www.luogu.com.cn/problem/P1064 我们可以只记录主键，和记录主键对应的依赖项 遍历时只有三种情况：
 * 1.不要当前 2.只要当前 3.既要当前，还要依赖项（对附属进行dp）
 * 这个版本适用于有多个附属的情况。
 */
public class ch05_有依赖的背包2 {
	static int[] w, v, pre;
	static int[][] master; // 记录每个主键的附属项
	static int[] cnts; // 记录每个主键的附属项的个数
	static int n, sum, cnt;

	public static void main(String[] args) {
		Reader sc = new Reader();
		sum = sc.nextInt();
		n = sc.nextInt();
		w = new int[n + 1];
		v = new int[n + 1];
		pre = new int[n + 1];
		cnts = new int[n + 1];
		master = new int[n + 1][n + 1];
		BitSet set = new BitSet();
		for (int i = 1; i <= n; i++) {
			w[i] = sc.nextInt();
			v[i] = sc.nextInt();
			pre[i] = sc.nextInt();
			if (pre[i] != 0) {
				master[pre[i]][++cnts[pre[i]]] = i;
			} else {
				set.set(i);
			}
		}
		cnt = set.cardinality();
		int res = dp(cnt, sum);
		System.out.println(res);
	}

	/**
	 * @param m:主要物品的个数
	 * @param sum
	 * @return
	 */
	public static int dp(int m, int sum) {
		int[][] slave = new int[m + 1][sum + 1]; // slave每个主物品对应的附属商品中，价钱为sum的最大值
		// s：主物品的起始位置
		for (int i = 1, s = 1; s <= n && i <= m; i++, s++) {
			while (s <= n && pre[s] != 0) {
				s++;
			}
			if (s > n)
				break;
			int max = sum - w[s]; // 这些附属商品能取到的最大容量
			int[][] dp = new int[2][max + 1];
			int prev, cur = 0;
			for (int j = 1; j <= cnts[s]; j++) { // 有j件附属商品时
				prev = cur;
				cur = (cur + 1) % 2;
				for (int k = 0; k <= max; k++) {
					dp[cur][k] = dp[prev][k]; // 不要这一件
					int index = master[s][j];
					if (k >= w[index]) { // 要这一件
						dp[cur][k] = Math.max(dp[cur][k], dp[prev][k - w[index]] + w[index]*v[index]);
					}
				}
			}
			slave[i] = dp[cur];
		}
		int[][] dp = new int[2][sum + 1];
		int prev, cur = 0;
		for (int i = 1, s = 1; s <= n && i <= m; i++, s++) {
			while (s <= n && pre[s] != 0)
				s++;
			if (s > n)
				break;
			prev = cur;
			cur = (cur + 1) % 2;
			for (int j = 1; j <= sum; j++) {
				dp[cur][j] = dp[prev][j]; // 不要当前
				if (j >= w[s]) {
					dp[cur][j] = Math.max(dp[cur][j], dp[prev][j - w[s]] + w[s]*v[s]); // 只要当前
					for (int k = 0, rest = j - w[s]; k <= rest; k++) { // 要附属的情况。这里以1来枚举价格，价格还可以用所有附属的最小公约数来枚举。
						dp[cur][j] = Math.max(dp[cur][j], dp[prev][j - w[s] - k]+ v[s]*w[s] + slave[i][k]);
					}
				}
			}
		}
		return dp[cur][sum];
	}
	static class Reader{
		StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		public int nextInt() {
			try {
				in.nextToken();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return (int) in.nval;
		}
	}
}
